#include <cassert>
#include <iostream>
#include <stack>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>{};

bitree *bt_copy(bitree *src)
{
    bitree *dst;

    if (!src) return NULL;
    dst = new bitree;
    assert(dst);
    *dst = *src;
    dst->lchild = bt_copy(src->lchild);
    dst->rchild = bt_copy(src->rchild);
    return dst;
}

struct snode{
    bitree *src;
    bitree *dst;
    int tag;
};

bitree *nr_bt_copy(bitree *rt)
{
    snode n;
    stack<snode> s;
    bitree *last = NULL;

    n.src = rt; n.dst = NULL; n.tag = 0;
    while (n.src || !s.empty()){
	if (n.src){
	    n.dst = new bitree;
	    assert(n.dst);
	    *n.dst = *n.src;
	    n.dst->lchild = n.dst->rchild = NULL;
	    s.push(n);
	    n.src = n.src->lchild; n.tag = 0;
	}
	else{
	    n = s.top(); s.pop();
	    if (n.tag == 0){
		if (last){
		    n.dst->lchild = last;
		    last = NULL;
		}
		n.tag = 1;
		s.push(n);
		n.src = n.src->rchild; n.tag = 0;
	    }
	    else{
		if (last){
		    n.dst->rchild = last;
		    last = NULL;
		}
		last = n.dst;
		n.src = NULL;
	    }
	}
    }

    return n.dst;
}

int main()
{
    bitree *src, *dst;

    bitree_create<bitree,char>(src, "ex46.txt");
    bitree_print(src);
    dst = nr_bt_copy(src);
    bitree_print(dst);
    bitree_destory(src);
    bitree_destory(dst);

    return 0;
}
